package leetcode;

import leetcode.Code7;

import java.util.*;

public class Code11_ {
    public class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    public static void main(String[] args) {
        Code11_ code11 = new Code11_();
        Code7 code7 = new Code7();
        TreeNode treeNode = code11.deserialize("{20,1,40,#,#,35}");
        List<Integer> list = code11.searchRange(treeNode,17,35);
        for (int a:list){
            System.out.println(" "+a);
        }
    }

    public List<Integer> searchRange(TreeNode root, int k1, int k2) {
        // write your code here
        ArrayList<Integer> needlist = new ArrayList<>();

        traverse(root,needlist,k1,k2);
        Collections.sort(needlist);
        return needlist;

    }
    public void traverse(TreeNode root,ArrayList<Integer> list,int k1,int k2){
        if(root==null){
            return;
        }
        int val = root.val;
        traverse(root.left,list,k1,k2);
        traverse(root.right,list,k1,k2);
        if (val>=k1&&val<=k2){
            list.add(val);
        }
    }
    public TreeNode deserialize(String data) {
        // write your code here
        String d = data.substring(1, data.length() - 1);
        data = d;
        String[] list = data.split(",");
        TreeNode[] tlist = new TreeNode[list.length];
        if (list[0].equals("#")) {
            return null;
        }
        tlist[0] = new TreeNode(Integer.parseInt(list[0]));
        for (int a = 1; a < list.length; a++) {
            int father = (a + 1) / 2 - 1;
            TreeNode item = null;
            if (!list[a].equals("#")) {
                item = new TreeNode(Integer.parseInt(list[a]));
            }
            if ((a + 1) % 2 == 0) {
                tlist[father].left = item;
            } else {
                tlist[father].right = item;
            }
            tlist[a] = item;
        }
        return tlist[0];
    }
}
